package 数组中出现次数超过一半的数字;
//题目描述
//数组中有一个数字出现的次数超过数组长度的一半，
// 请找出这个数字。
// 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
// 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array)
    {
        //笨方法：先排序，首位设置指针，下一位相同的计数，不同的就重新计数
        //方法一，统计学中中位数的方法，如果一个数字出现次数超过一半，那它一定位于排序之后的
        //数组的n/2的位置上，但又不必使用复杂度最好也是O(nlogn)的完全排序，只要使用快速排序
        //将n/2处的数字归位就好了，任意选择一个数字，比它小的在左，比他大的在右，看下标是否是
        //n/2，是的话就得到中位数，大于的话，中位数在左边。小于的话，中位数在右边，递归的方法。
        //如果不存在次数超过一半的数字的判断
        //方法二，计数法，与下个数字相同时加1，不同减1，为0时读取下一个数，times置为1
        //一个数次数超过一半，也就是比其他数次加起来的次数还要多。

        //判断输入
        if(array==null||array.length==0)
            return 0;

        int times=1;
        int maxtimes=0;
        int result=0;
        for (int i = 1; i < array.length; i++)
        {
            if (array[i-1]==array[i])
            {
                times++;
                if (maxtimes<times)
                {
                    maxtimes = times;
                    result=array[i];
                }
            }
            if (array[i-1]!=array[i])
            {
                times--;
            }
            if (times==0)
            {
                times=1;
            }

        }
        if (array.length==1)
            return array[0];
        if (checkCount(array,result))
            return result;
        else
            return 0;
    }
    //判断次数是否为一半以上
    public boolean checkCount(int[] array,int result)
    {
        //判断输入
        int times=0;
        for (int i = 0; i < array.length; i++)
        {
            if (result==array[i])
                times++;
        }
        if (times*2>array.length)
            return true;
        else
            return false;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        int[] test =new int[]{1,2,2};
        System.out.println(solution.MoreThanHalfNum_Solution1(test));
    }
    //快排Partition的方法，找到中位数
    public int Partition(int[] arr,int start,int end)
    {
        int index=(int)(Math.random()*(end-start));
        int small=start-1;
        swap(arr,index,end);
        for (index = start; index<end; index++)
        {
            if (arr[index]<arr[end])
            {
                ++small;
                if (arr[index]!=arr[small])
                    swap(arr,index,small);
            }
        }
        small++;
        swap(arr,small,end);
        return small;
    }
    public void swap(int[] arr,int index1,int index2)
    {
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
    public int MoreThanHalfNum_Solution1(int[] array)
    {
        if (array==null||array.length==0)
            return 0;
        int res=helper(array,0,array.length-1);
        if (res!=-1)
            return res;
        else
            return 0;

    }
    public int helper(int[] arr,int start,int end)
    {
        if (start==end)
            return -1;
        int index=Partition(arr,start,end);
        if (index==(end-start+1)/2)
            return arr[index];
        else if (index>(end-start+1)/2)
            return helper(arr,start,index-1);
        else
            return helper(arr,index+1,end);
    }

}
